package com.yanceysong.codetop.s21_s30;

import com.yanceysong.common.ListNode;

public class S26_Hard_23_合并K个排序链表 {
    /**
     * LeetCode链接
     * <a href="https://leetcode.cn/problems/merge-k-sorted-lists/description/">...</a>
     * <p>
     * 给你一个链表数组，每个链表都已经按升序排列。
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     * <p>
     * 示例1：
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     * .    1 -> 4 -> 5,
     * .    1 -> 3 -> 4,
     * .    2 -> 6
     * ]
     * 将它们合并到一个有序链表中得到：
     * 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
     * <p>
     * 示例2：
     * 输入：lists = []
     * 输出：[]
     * <p>
     * 示例3：
     * 输入：lists = [[]]
     * 输出：[]
     * <p>
     * 提示：
     * k == lists.length
     * 0 <= k <= 10^4
     * 0 <= lists[i].length <= 500
     * -10^4 <= lists[i][j] <= 10^4
     * lists[i] 按 升序 排列
     * lists[i].length 的总和不超过 10^4
     * <p>
     * 解题：
     * {@link com.yanceysong.codetop.s21_s30.S26_Hard_23_合并K个排序链表#mergeKLists(com.yanceysong.common.ListNode[])}
     * <p>
     * ==================== 合并K个升序链表算法图解 ====================
     * <p>
     * 算法思路：分治法（Divide and Conquer）+ 递归合并
     * 1. 使用分治思想将K个链表分成两部分
     * 2. 递归地合并左半部分和右半部分
     * 3. 最后合并两个已排序的链表
     * 4. 利用二分的思想减少合并次数，提高效率
     * <p>
     * 执行示例：lists = [[1,4,5],[1,3,4],[2,6]]
     * <p>
     * 初始状态：
     * lists[0]: 1  ->  4  ->  5
     * lists[1]: 1  ->  3  ->  4
     * lists[2]: 2  ->  6
     * <p>
     * 分治过程详解：
     * <p>
     * 第1层：merge(lists, 0, 2)
     * ├── left=0, right=2, mid=1
     * ├── 递归调用：merge(lists, 0, 1) 处理左半部分
     * └── 递归调用：merge(lists, 2, 2) 处理右半部分
     * <p>
     * 第2层左分支：merge(lists, 0, 1)
     * ├── left=0, right=1, mid=0
     * ├── 递归调用：merge(lists, 0, 0)  ->  返回lists[0] = [1,4,5]
     * ├── 递归调用：merge(lists, 1, 1)  ->  返回lists[1] = [1,3,4]
     * └── 合并两个链表：mergeTwoLists([1,4,5], [1,3,4])
     * <p>
     * 第2层右分支：merge(lists, 2, 2)
     * └── left=right=2，直接返回lists[2] = [2,6]
     * <p>
     * 合并过程图解：
     * <p>
     * 步骤1：合并[1,4,5]和[1,3,4]
     * 1  ->  4  ->  5
     * 1  ->  3  ->  4
     * ↓
     * 比较过程：
     * 1 == 1，选择第一个1: 1  ->  ?
     * 4 > 3，选择3: 1  ->  3  ->  ?
     * 4 == 4，选择第一个4: 1  ->  3  ->  4  ->  ?
     * 剩余[5]和[4]: 4 < 5，选择4: 1  ->  3  ->  4  ->  4  ->  ?
     * 剩余[5]: 1  ->  3  ->  4  ->  4  ->  5
     * <p>
     * 结果：1  ->  3  ->  4  ->  4  ->  5
     * <p>
     * 步骤2：合并[1,3,4,4,5]和[2,6]
     * 1  ->  3  ->  4  ->  4  ->  5
     * 2  ->  6
     * ↓
     * 比较过程：
     * 1 < 2，选择1: 1  ->  ?
     * 3 > 2，选择2: 1  ->  2  ->  ?
     * 3 < 6，选择3: 1  ->  2  ->  3  ->  ?
     * 4 < 6，选择4: 1  ->  2  ->  3  ->  4  ->  ?
     * 4 < 6，选择4: 1  ->  2  ->  3  ->  4  ->  4  ->  ?
     * 5 < 6，选择5: 1  ->  2  ->  3  ->  4  ->  4  ->  5  ->  ?
     * 剩余[6]: 1  ->  2  ->  3  ->  4  ->  4  ->  5  ->  6
     * <p>
     * 最终结果：1  ->  2  ->  3  ->  4  ->  4  ->  5  ->  6
     * <p>
     * ==================== 算法复杂度分析 ====================
     * <p>
     * 分治法优势分析：
     * <p>
     * 方法对比：
     * 1. 暴力法：逐一合并，时间复杂度O(k²n)
     * 2. 分治法：二分合并，时间复杂度O(kn log k)
     * <p>
     * 分治法过程：
     * - 第1轮：k个链表  ->  k/2个链表（每次合并2个）
     * - 第2轮：k/2个链表  ->  k/4个链表
     * - ...
     * - 第log k轮：2个链表  ->  1个链表
     * <p>
     * 每轮合并的总节点数：n（所有链表节点总数）
     * 总轮数：log k
     * 时间复杂度：O(n log k)
     * 空间复杂度：O(log k)（递归调用栈）
     * <p>
     * 关键优化点：
     * 1. 使用分治减少合并轮数
     * 2. 递归合并两个有序链表
     * 3. 避免重复遍历已合并的链表
     * <p>
     * ================================================================
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 边界检查：空数组或null直接返回null
        if (lists == null || lists.length == 0) return null;

        // 使用分治法合并所有链表
        return merge(lists, 0, lists.length - 1);
    }

    /**
     * 分治法核心方法：递归合并指定范围内的链表
     *
     * @param lists 链表数组
     * @param left  左边界索引
     * @param right 右边界索引
     * @return 合并后的链表头节点
     * <p>
     * 算法思路：
     * 1. 递归终止条件：当left == right时，只有一个链表，直接返回
     * 2. 分治策略：将区间[left, right]分成两部分
     * 3. 递归合并：分别合并左半部分和右半部分
     * 4. 合并结果：将两个已排序的链表合并成一个
     */
    private ListNode merge(ListNode[] lists, int left, int right) {
        // 递归终止条件：只有一个链表时直接返回
        if (left == right) return lists[left];

        // 计算中点，避免整数溢出
        int mid = left + (right - left) / 2;

        // 分治策略：递归合并左半部分和右半部分
        ListNode l1 = merge(lists, left, mid);           // 合并[left, mid]
        ListNode l2 = merge(lists, mid + 1, right);      // 合并[mid+1, right]

        // 合并两个已排序的链表
        return mergeTwoLists(l1, l2);
    }

    /**
     * 合并两个有序链表的递归实现
     *
     * @param l1 第一个有序链表
     * @param l2 第二个有序链表
     * @return 合并后的有序链表头节点
     * <p>
     * 算法思路：
     * 1. 递归终止条件：其中一个链表为空时，返回另一个链表
     * 2. 比较策略：比较两个链表当前节点的值
     * 3. 递归构建：选择较小值的节点，递归处理剩余部分
     * 4. 链表连接：将选中节点的next指向递归结果
     */
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 递归终止条件：其中一个链表为空
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // 比较当前节点值，选择较小的节点作为当前结果
        if (l1.val < l2.val) {
            // l1的值较小，选择l1，递归处理l1.next和l2
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            // l2的值较小或相等，选择l2，递归处理l1和l2.next
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public static void main(String[] args) {
        S26_Hard_23_合并K个排序链表 solution = new S26_Hard_23_合并K个排序链表();

        System.out.println("=== 合并K个升序链表测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同规模链表测试
        System.out.println("\n--- 测试3: 不同规模链表测试 ---");
        testDifferentScales(solution);

        // 测试4: 特殊情况测试
        System.out.println("\n--- 测试4: 特殊情况测试 ---");
        testSpecialCases(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        // 测试6: 复杂场景测试
        System.out.println("\n--- 测试6: 复杂场景测试 ---");
        testComplexScenarios(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S26_Hard_23_合并K个排序链表 solution) {
        // 示例1: [[1,4,5],[1,3,4],[2,6]]  ->  [1,1,2,3,4,4,5,6]
        ListNode[] lists1 = {
                createList(new int[]{1, 4, 5}),
                createList(new int[]{1, 3, 4}),
                createList(new int[]{2, 6})
        };
        int[] expected1 = {1, 1, 2, 3, 4, 4, 5, 6};
        testMergeKLists(solution, lists1, expected1, "题目示例1");

        // 示例2: []  ->  []
        ListNode[] lists2 = {};
        int[] expected2 = {};
        testMergeKLists(solution, lists2, expected2, "题目示例2(空数组)");

        // 示例3: [[]]  ->  []
        ListNode[] lists3 = {null};
        int[] expected3 = {};
        testMergeKLists(solution, lists3, expected3, "题目示例3(空链表)");

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S26_Hard_23_合并K个排序链表 solution) {
        // 测试1: null输入
        ListNode result1 = solution.mergeKLists(null);
        System.out.println("null输入: null  ->  " + (result1 == null ? "null" : "非null") + " (期望: null)");
        assert result1 == null : "null输入测试失败";

        // 测试2: 单个链表
        ListNode[] lists2 = {createList(new int[]{1, 2, 3})};
        int[] expected2 = {1, 2, 3};
        testMergeKLists(solution, lists2, expected2, "单个链表");

        // 测试3: 单个空链表
        ListNode[] lists3 = {null};
        int[] expected3 = {};
        testMergeKLists(solution, lists3, expected3, "单个空链表");

        // 测试4: 两个链表
        ListNode[] lists4 = {
                createList(new int[]{1, 3, 5}),
                createList(new int[]{2, 4, 6})
        };
        int[] expected4 = {1, 2, 3, 4, 5, 6};
        testMergeKLists(solution, lists4, expected4, "两个链表");

        // 测试5: 包含空链表的混合情况
        ListNode[] lists5 = {
                createList(new int[]{1, 3}),
                null,
                createList(new int[]{2, 4})
        };
        int[] expected5 = {1, 2, 3, 4};
        testMergeKLists(solution, lists5, expected5, "包含空链表的混合");

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同规模的链表
     */
    private static void testDifferentScales(S26_Hard_23_合并K个排序链表 solution) {
        // 测试1: 多个单节点链表
        ListNode[] lists1 = {
                createList(new int[]{5}),
                createList(new int[]{1}),
                createList(new int[]{3}),
                createList(new int[]{2}),
                createList(new int[]{4})
        };
        int[] expected1 = {1, 2, 3, 4, 5};
        testMergeKLists(solution, lists1, expected1, "多个单节点链表");

        // 测试2: 不同长度链表
        ListNode[] lists2 = {
                createList(new int[]{1}),
                createList(new int[]{2, 3}),
                createList(new int[]{4, 5, 6}),
                createList(new int[]{7, 8, 9, 10})
        };
        int[] expected2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        testMergeKLists(solution, lists2, expected2, "不同长度链表");

        // 测试3: 大量短链表
        ListNode[] lists3 = new ListNode[10];
        for (int i = 0; i < 10; i++) {
            lists3[i] = createList(new int[]{i * 2, i * 2 + 1});
        }
        int[] expected3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
        testMergeKLists(solution, lists3, expected3, "大量短链表");

        System.out.println("✓ 不同规模链表测试通过");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S26_Hard_23_合并K个排序链表 solution) {
        // 测试1: 包含负数的链表
        ListNode[] lists1 = {
                createList(new int[]{-2, 0, 2}),
                createList(new int[]{-3, -1, 1}),
                createList(new int[]{-1, 3})
        };
        int[] expected1 = {-3, -2, -1, -1, 0, 1, 2, 3};
        testMergeKLists(solution, lists1, expected1, "包含负数");

        // 测试2: 相同元素的链表
        ListNode[] lists2 = {
                createList(new int[]{1, 1, 1}),
                createList(new int[]{1, 1, 1}),
                createList(new int[]{1, 1, 1})
        };
        int[] expected2 = {1, 1, 1, 1, 1, 1, 1, 1, 1};
        testMergeKLists(solution, lists2, expected2, "相同元素");

        // 测试3: 递增序列
        ListNode[] lists3 = {
                createList(new int[]{1, 4, 7}),
                createList(new int[]{2, 5, 8}),
                createList(new int[]{3, 6, 9})
        };
        int[] expected3 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        testMergeKLists(solution, lists3, expected3, "递增序列");

        // 测试4: 逆序输入
        ListNode[] lists4 = {
                createList(new int[]{7, 8, 9}),
                createList(new int[]{4, 5, 6}),
                createList(new int[]{1, 2, 3})
        };
        int[] expected4 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        testMergeKLists(solution, lists4, expected4, "逆序输入");

        // 测试5: 大数值
        ListNode[] lists5 = {
                createList(new int[]{9999, 10000}),
                createList(new int[]{-10000, -9999}),
                createList(new int[]{0})
        };
        int[] expected5 = {-10000, -9999, 0, 9999, 10000};
        testMergeKLists(solution, lists5, expected5, "大数值");

        System.out.println("✓ 特殊情况测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S26_Hard_23_合并K个排序链表 solution) {
        // 测试1: 中等规模
        System.out.println("性能测试1: 10个链表，每个10个节点");
        testPerformanceCase(solution, 10, 10);

        // 测试2: 较大规模
        System.out.println("性能测试2: 50个链表，每个20个节点");
        testPerformanceCase(solution, 50, 20);

        // 测试3: 大规模
        System.out.println("性能测试3: 100个链表，每个50个节点");
        testPerformanceCase(solution, 100, 50);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S26_Hard_23_合并K个排序链表 solution, int listCount, int nodeCount) {
        // 创建测试数据
        ListNode[] lists = new ListNode[listCount];
        for (int i = 0; i < listCount; i++) {
            int[] values = new int[nodeCount];
            for (int j = 0; j < nodeCount; j++) {
                values[j] = i * nodeCount + j;
            }
            lists[i] = createList(values);
        }

        long startTime = System.currentTimeMillis();
        ListNode result = solution.mergeKLists(lists);
        long endTime = System.currentTimeMillis();

        // 验证结果
        assert result != null : "性能测试：结果不应为空";
        int[] resultArray = listToArray(result);
        assert resultArray.length == listCount * nodeCount : "性能测试：结果长度不正确";
        assert isSorted(resultArray) : "性能测试：结果应该是有序的";

        System.out.println("  链表数量: " + listCount +
                ", 每个链表节点数: " + nodeCount +
                ", 总节点数: " + (listCount * nodeCount) +
                ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度合理
        assert (endTime - startTime) < 5000 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 测试复杂场景
     */
    private static void testComplexScenarios(S26_Hard_23_合并K个排序链表 solution) {
        // 测试1: 交错分布
        ListNode[] lists1 = {
                createList(new int[]{1, 5, 9}),
                createList(new int[]{2, 6, 10}),
                createList(new int[]{3, 7, 11}),
                createList(new int[]{4, 8, 12})
        };
        int[] expected1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        testMergeKLists(solution, lists1, expected1, "交错分布");

        // 测试2: 一个很长链表 + 多个短链表
        ListNode[] lists2 = {
                createList(new int[]{1, 3, 5, 7, 9, 11, 13, 15}),
                createList(new int[]{2}),
                createList(new int[]{4}),
                createList(new int[]{6}),
                createList(new int[]{8})
        };
        int[] expected2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15};
        testMergeKLists(solution, lists2, expected2, "长短链表混合");

        // 测试3: 多个空链表 + 非空链表
        ListNode[] lists3 = {
                null,
                createList(new int[]{1, 3, 5}),
                null,
                createList(new int[]{2, 4, 6}),
                null
        };
        int[] expected3 = {1, 2, 3, 4, 5, 6};
        testMergeKLists(solution, lists3, expected3, "多空链表混合");

        System.out.println("✓ 复杂场景测试通过");
    }

    /**
     * 创建链表的辅助方法
     */
    private static ListNode createList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }

        ListNode head = new ListNode(values[0]);
        ListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }

        return head;
    }

    /**
     * 将链表转换为数组的辅助方法
     */
    private static int[] listToArray(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        // 先计算链表长度
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        // 转换为数组
        int[] result = new int[length];
        current = head;
        for (int i = 0; i < length; i++) {
            result[i] = current.val;
            current = current.next;
        }

        return result;
    }

    /**
     * 打印数组的辅助方法
     */
    private static void printArray(int[] arr) {
        if (arr.length == 0) {
            System.out.print("[]");
            return;
        }

        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(",");
            }
        }
        System.out.print("]");
    }

    /**
     * 测试合并K个链表的辅助方法
     */
    private static void testMergeKLists(S26_Hard_23_合并K个排序链表 solution, ListNode[] lists, int[] expected, String description) {
        // 创建输入的副本用于显示（因为原链表会被修改）
        int[][] inputArrays = new int[lists.length][];
        for (int i = 0; i < lists.length; i++) {
            inputArrays[i] = listToArray(lists[i]);
        }

        ListNode result = solution.mergeKLists(lists);
        int[] actual = listToArray(result);

        System.out.print(description + " - 输入: [");
        for (int i = 0; i < inputArrays.length; i++) {
            printArray(inputArrays[i]);
            if (i < inputArrays.length - 1) {
                System.out.print(",");
            }
        }
        System.out.print("]  ->  输出: ");
        printArray(actual);
        System.out.print(" (期望: ");
        printArray(expected);
        System.out.println(")");

        assert java.util.Arrays.equals(actual, expected) : description + "测试失败";
    }

    /**
     * 检查数组是否有序的辅助方法
     */
    private static boolean isSorted(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return true;
        }

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }

        return true;
    }
}

